import java.util.Scanner;
import java.lang.String;

public class TestDemo {

    //public static void main1(String[] args) {
        /*System.out.println(5/2);
        System.out.println(5.0/2);
        System.out.println((float)5/2);
        System.out.println((float)(5/2));
        */

        /*System.out.println(10%3);
        System.out.println(-10%3);
        System.out.println(10%-3);
        System.out.println(-10%-3);
        */

        /*int i = 10;
        i = i++;
        System.out.println(i);
        */

        /*int a = 10;
        int b = 20;
        System.out.println(a>b);
        System.out.println(a<b);
        */

        /*boolean flag = true;
        System.out.println(!flag);
        */

        /*Scanner scan  = new Scanner(System.in);
        int a = scan.nextInt();
        System.out.println(a);
        */

        /*Scanner scan = new Scanner(System.in);
        int a = 0;
        String str = "";
        a = scan.nextInt();
        str = scan.next();
        System.out.println(a);
        System.out.println(str);
        */

        /*Scanner scan = new Scanner(System.in);
        int a = 0;
        while (scan.hasNextInt()) {
            a = scan.nextInt();
            System.out.println(a);
        }
        */

        /*int a = 0;
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextInt()) {
            a = scan.nextInt();
            switch (a) {
                case 1:
                    System.out.println(a);
                    break;

                case 2:
                    System.out.println(a);
                    break;

                default:
                    System.out.println("Wrong number!");
                    break;
            }
        }
        scan.close();
        */

        /*int i = 1;
        int res = 0;
        int ret = 1;
        while (i <= 5) {
            ret *= i;
            res += ret;
            i++;

        } 
        System.out.println(res);
        */

        /*int Age = 0;
        Scanner scan = new Scanner(System.in);
        while (scan.hasNextInt()) {
            Age = scan.nextInt();
            if (Age<=18) {
                System.out.println("Teen");

            } else if (Age>18 && Age<=28) {
                System.out.println("Young");

            } else if (Age>28 && Age<=55) {
                System.out.println("Middle");

            } else {
                System.out.println("Old");

            }

        }
        scan.close();
        */

        /*int num = 0;
        int i = 2;
        Scanner scan = new Scanner(System.in);
        num = scan.nextInt();
        while (i < num) {
            if (num%i == 0) {
                System.out.println(num + " is not a prime");
                break;
            } 
            i++;

        }
        scan.close();
        */

        /*
        int i = 1;
        int j = 2;
        while (i <= 100) {
            if (i == 1) {
                System.out.print(i+" ");

            }

            while (j < i) {

                if (i%j == 0) {
                    break;
                }
                j++;

            }
            if (j == i) {
                System.out.print(i+" ");
            }
            j = 2;
            i++;
        }*/

        /*
        int year = 1000;
        while (year <= 2000) {
            if ((year%4 == 0) && (year%100 != 0) || (year%400 == 0)) {
                System.out.print(year+" ");
    
            }
            year++;
        }
        */

        /*
        int i = 1;
        int j = 1;
        while (i <= 9) {
            while (j <= i) {
                System.out.print(j + " * " + i + " = " + (j*i) + " ");
                j++;
            }
            System.out.println("");
            j = 1;
            i++;
        }
        */
        
        /*
        int a = 0;
        int b = 0;
        int c = 0;
        Scanner scan = new Scanner(System.in);
        a = scan.nextInt();
        b = scan.nextInt();
        while(b > 0) {
            c = a % b;
            a = b;
            b = c;
        }

        System.out.println(a);
        scan.close();
        */

        /*
        double i = 1.0;
        double sum = 0;
        int j = 1;
        int trans = 1;
        while (j <= 100) {
            sum += (i / j)*trans;
            j++;
            trans = -trans;

        }
        System.out.println(sum);
        */

        /*
        int i = 1, temp = 0,sum = 0;
        while(i <= 999) {
            temp = i;
            while (temp != 0) {
                sum += Math.pow(temp%10,3);
                temp /= 10;
            }
            if (i == sum) {
                System.out.println(sum+" ");

            }
            sum = 0;
            i++;

        }
        */

        /*
        int num = 7;
        int count = 0;
        while (num != 0) {
            if ((num & 1) == 1) {
                count++;

            }
            num >>= 1;
        }
        System.out.println(count);
        */

        /*
        String str1 = "";
        String str2 = "";
        Scanner scan = new Scanner(System.in);
        str1 = scan.nextLine();
        str2 = scan.nextLine();
        if (str1 .equals(str2)) {
            System.out.println("str1 equals str2");
        }
        scan.close();
        */


    //}

    /*
    public static int maxNum(int num1, int num2) {
        return num1 > num2 ? num1 : num2;
    }

    public static void main(String[] args) {

        int num1 = 0, num2 = 0;
        Scanner scan = new Scanner(System.in);
        num1 = scan.nextInt();
        num2 = scan.nextInt();
        int ret = maxNum(num1, num2);
        System.out.println(ret);
        scan.close();

    }
    */

    /*
    public static int factor(int i) {
        int ret = 1;

        for (int j = 1;j <= i;j++) {
            ret *= j;
        }

        return ret;
    }

    public static void main(String[] args) {
        int i = 0, sum = 0;

        for (i = 0;i < 6;i++) {
            sum += factor(i);
        }

        System.out.println(sum);
    }
    */

    /*
    public static int sum(int a, int b) {
        return a+b;
    }

    public static double sum(double a, double b) {
        return a+b;
    }

    public static void main(String[] args) {
        int a = 1, b = 2;
        double c = 1.1, d = 3.5;
        System.out.println(sum(a,b));
        System.out.println(sum(c,d));
    }
    */
    /*
    public static int sum(int a,int b) {
        return a+b;
    }

    public static int sum(int a,int b,int c) {
        return a+b+c;
    }

    public static int sum(int a, int b, int c, int d) {
        return a+b+c+d;
    }
    */

    /*
    public static int sum(int num) {
        if(num == 1) {
            return 1;
        }

        return num + sum(num - 1);
    }*/

    /*
    public static int sum(int num) {
        if(num < 10) {
            return num;
        }
        return num % 10 + sum(num/10);
    }
    */

    /*
    public static void move(char A, char C) {

        System.out.println(A + " --> " + C) ;
    }

    public static void haNoi(int n, char A, char B, char C) {
        if(n == 1) {
            move(A, C);
            return;
        } else {
            haNoi(n-1, A, C, B);
            move(A,C);
            haNoi(n-1, B, A ,C);
        }
    }

    public static void main(String[] args) {
        int n = 0;
        char A = 'a';
        char B = 'b';
        char C = 'c';
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        haNoi(n, A, B, C);
        scan.close();
    }
    */

    /*
    import java.util.Scanner;

public class Main {
    
    public static void main(String []args) {
        long a = 0L, b = 0L, c = 0L;
        int n = 0;
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for (int i = 1;i <= n;i++) {
            
            a = scan.nextLong();
            b = scan.nextLong();
            c = scan.nextLong();
            
            if (a + b > c) {
                System.out.println("Case #" + i + ": true");
                
            } else {
                System.out.println("Case #" + i + ": false");
                
            }
        }
        scan.close();
    }
    
}
    */

    /*
    import java.util.Scanner;
import java.lang.Math;

public class Main {
    
    public static boolean isPrime(int i) {
        
        int j = 0;
        for(j = 2;j <= Math.sqrt(i);j++) {
            if(i %j == 0) {
            return false;
            }
        }
        return true;
    }
    
    public static void main(String []args) {
    
        int n = 0, i = 0, count = 0;
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for (i = 3;i <= n-2;i++) {
            
            if (isPrime(i) && isPrime(i+2)) {
                count++;
            }
        }
        scan.close();
        System.out.println(count);
    }
}
    */

    /*
    import java.util.Scanner;

        public class Main {
    
    public static void main(String []args) {
        Scanner scan = new Scanner(System.in);
        int n = 0, i = 0;
        n = scan.nextInt();
        while (n != 1) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                n = (3*n + 1) / 2;
            }
            i++;
        }
        scan.close();
        System.out.println(i);
    }
}
    */


    /*
    https://onedrive.live.com/view.aspx?resid=64BC5985E72D1960%21123&id=documents&wd=target%28Java%20EE.one%7C291FC879-0C0C-4709-9CE1-08CED32A604B%2FJAVA_Learing_2_26%7CAC56DFC8-2E18-435E-A11F-12F453193BF3%2F%29
    onenote:https://d.docs.live.net/64bc5985e72d1960/文档/志轩%20的笔记本/Java%20EE.one#JAVA_Learing_2_26&section-id={291FC879-0C0C-4709-9CE1-08CED32A604B}&page-id={AC56DFC8-2E18-435E-A11F-12F453193BF3}&end
     */
}